﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//day33-01 牛客：跳台阶扩展问题，题号：2361300
//解法：1、预处理 2、找规律
//int main()
//{
//    int n;
//    cin >> n;
//    //方法1：
//    // int ret=1,sum=1;
//    // for(int i=2;i<=n;i++)
//    // {
//    //     ret=sum+1;
//    //     sum+=ret;
//    // }
//    //方法2：
//    int ret = pow(2, n - 1);
//    cout << ret << endl;
//    return 0;
//}


//day33-02 牛客：包含不超过两种字符的最⻓⼦串，题号：2454794
//解法：滑动窗口
//int main()
//{
//    string s;
//    cin >> s;
//    int count = 0;
//    int hash[26] = { 0 };
//    int ret = 0;
//    for (int left = 0, right = 0; right < s.size(); right++)
//    {
//        if (hash[s[right] - 'a'] == 0)
//        {
//            count++;
//        }
//        hash[s[right] - 'a']++;
//        while (count > 2)
//        {
//            if (--hash[s[left++] - 'a'] == 0)
//                count--;
//        }
//        ret = max(ret, right - left + 1);
//    }
//    cout << ret << endl;
//    return 0;
//}



//day33-03 牛客：字符串的排列，题号：23291
//解法：DFS
//vector<string> ret;
//string path;
//bool vis[11] = { 0 };
//unordered_set<string> hash;
//vector<string> Permutation(string str)
//{
//    dfs(str, 0);
//    return ret;
//}
//void dfs(string str, int pos)
//{
//    if (pos == str.size() && hash.count(path) == 0)
//    {
//        ret.push_back(path);
//        hash.insert(path);
//        return;
//    }
//    for (int i = 0; i < str.size(); i++)
//    {
//        if (vis[i] == false)
//        {
//            vis[i] = true;
//            path += str[i];
//            dfs(str, pos + 1);
//            vis[i] = false;
//            path.pop_back();
//        }
//    }
//}


